package summary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/2 22:29
 */
public class Title448 {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        int cur = 0;
        while (cur < n) {
            //判断 相应的位置是否为相应的数  nums[i] == i
            if (nums[cur] - 1 == cur) {
                cur++;
            }else{
                int targetIndex = nums[cur] - 1;
                if (nums[cur] == nums[targetIndex]) {
                    cur++;
                }else{
                    //交换
                    int temp = nums[cur];
                    nums[cur] = nums[targetIndex];
                    nums[targetIndex] = temp;
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] - 1 != i) {
                result.add(i);
            }
        }
        return result;
    }

    public List<Integer> findDisappearedNumbers1(int[] nums) {
        int n = nums.length;
        for (Integer temp : nums) {
            int x = (temp - 1) % n;
            nums[x] += n;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                result.add(nums[i]);
            }
        }
        return result;
    }

    public static void main(String[] args) {

    }
}
